/*******************************************************************************
filename      CVector.h
author        Craig Williams

Brief Description:
  dll safe container, similar to std::vector; however, it does several things
    differently.

  Highlights:
    erase()   - erase() does not preserve sort order. Rather, the last element
                  is used to overwrite the element that is being erased. This
                  is drastically faster then shifting over all the elements
                  after the erased object.
    raw copy  - When elements are shifted/moved around, a raw copy is
                  performed. std::vector will call the copy constructor and
                  destructor for all elements that move. This is extremely
                  slow, especially when the vector needs to grow.
                This can be dangerious if there is a pointer to a element inside
                  a vector, or a element stores a pointer to it's self; however,
                  those cases are extremely rare and generally a bad idea to
                  begin with.
    realloc() - This class uses the *alloc() family. realloc() can perform
                  optimizations at the kernel level (just expand the memory)
                  that you cannot do with new/delete. As such, in it's best
                  case, it'll be extrmely faster. In the worst case, it'll be
                  the same as new/delete.
*******************************************************************************/
#ifdef CVECTOR_H    // Only compile if this file was included by CVector.h

#if CVECTOR_BOUNDS_CHECKING
  #include <stdio.h>
#endif

#include <new>      // Placment new is not declared by default

#include "CVectorHelpers.h"
/*******************************************************************************
   Function: CVector()

Description: See Init()
*******************************************************************************/
template<typename T>
CVector<T>::CVector(int initsize, float growth)
{
  mData    = 0;
  Num      = 0;
  Cur      = 0;
  InitSize = initsize <= 1 ? 2 : initsize;
  Growth   = growth <= 1.0f ? 1.5f : growth;

  Realloc  = CVectorRealloc;
  Free     = CVectorFree;

  AllocData();
}

/*******************************************************************************
   Function: ~CVector()

Description: Frees the memory used by the vector
*******************************************************************************/
template<typename T>
CVector<T>::~CVector()
{
  if(!mData)
    return;

  for(unsigned int i = 0; i < Cur; ++i)
    mData[i].~T();

  Free(mData);
}

/*******************************************************************************
   Function: CVector()

Description: See operator=
*******************************************************************************/
template<typename T>
CVector<T>::CVector(const CVector<T> &vec)
{
  mData   = 0;
  Cur     = 0;

  Realloc = CVectorRealloc;
  Free    = CVectorFree;

  *this   = vec;
}

/*******************************************************************************
   Function: operator=

Description: Makes a duplicate of another vector, includeing all the data
               that the specified vector contains.

     Inputs: &vec - Vector to duplicate

    Outputs: Refrence to the current vector
*******************************************************************************/
template<typename T>
CVector<T> &CVector<T>::operator=(const CVector<T> &vec)
{
  unsigned int i;

  for(i = 0; i < Cur; ++i)
    mData[i].~T();

  Growth   = vec.Growth;
  Num      = vec.Num;
  Cur      = vec.Cur;
  InitSize = vec.InitSize;
  mData  = static_cast<T *>(Realloc(mData, sizeof(T) * (Num + 1)));

  for(i = 0; i < Cur; ++i)
    new (mData + i) T(vec.mData[i]);

  if(!mData)
    AllocData();

  return *this;
}

/*******************************************************************************
   Function: push_back()

Description: Adds a new element to the vector. This function will destory any
               sort order.

     Inputs: &data - Refrence to the data to add to the vector

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::push_back(const T &data)
{
  new (mData + Cur++) T(data);

  if(Cur == Num)
    AllocData();
}

/*******************************************************************************
   Function: push_last()

Description: Duplicates the last item in the vector, and then pushes it back.
               This funciton is faster and safter then calling push_back(back())

     Inputs: N/A

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::push_last(void)
{
  #if CVECTOR_BOUNDS_CHECKING
    if(!Cur)
    {
      printf("ERROR: CVector::push_last(): No Elements in the vector\n");
      return;
    }
  #endif

  new (mData + Cur) T(mData[Cur - 1]);
  ++Cur;

  if(Cur == Num)
    AllocData();
}

/*******************************************************************************
   Function: pop_back()

Description: Removes the last item from the vector

     Inputs: N/A

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::pop_back(void)
{
  #if CVECTOR_BOUNDS_CHECKING
    if(!Cur)
    {
      printf("ERROR: CVector::pop_back(): Poping a empty vector\n");
      return;
    }
  #endif

  mData[--Cur].~T();
}

/*******************************************************************************
   Function: erase()

Description: Removes the specified element from the vector. If the vector is
               sorted, the sort order will be preserved.

     Inputs: index - Numerical index of the item to remove

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::erase(unsigned int index)
{
  #if CVECTOR_BOUNDS_CHECKING
    if(index >= Cur)
    {
      printf("ERROR: CVector::erase: Erasing a invalid index\n");
      return;
    }
  #endif

  mData[index].~T();

  if(index != --Cur)
    CVectorMemcpy(mData + index, mData + Cur, sizeof(T));
}

/*******************************************************************************
   Function: operator[]

Description: Retrieves the requested element from the vector

     Inputs: index - Index of the element to return

    Outputs: Refrence to the requested object
*******************************************************************************/
template<typename T>
T &CVector<T>::operator[](unsigned int index) const
{
  return at(index);
}

/*******************************************************************************
   Function: at()

Description: See operator[]
*******************************************************************************/
template<typename T>
T &CVector<T>::at(unsigned int index) const
{
  #if CVECTOR_BOUNDS_CHECKING
    if(index >= Cur)
    {
      printf("ERROR: CVector::operator[]: Accessing a invalid index\n");
      return mData[index];
    }
  #endif

  return mData[index];
}

/*******************************************************************************
   Function: front()

Description: Returns the first item in the vector

     Inputs: N/A

    Outputs: Refrence to the first element in the vector
*******************************************************************************/
template<typename T>
T &CVector<T>::front(void) const
{
  #if CVECTOR_BOUNDS_CHECKING
    if(!Cur)
    {
      printf("ERROR: CVector::front(): Empty vector\n");
      return mData[0];
    }
  #endif

  return mData[0];
}

/*******************************************************************************
   Function: back()

Description: Returns the last element in the vector

     Inputs: N/A

    Outputs: Refrence to the last element in the vector
*******************************************************************************/
template<typename T>
T &CVector<T>::back(void) const
{
  #if CVECTOR_BOUNDS_CHECKING
    if(!Cur)
    {
      printf("ERROR: CVector::front(): Empty vector\n");
      return mData[0];
    }
  #endif

  return mData[Cur - 1];
}

/*******************************************************************************
   Function: size()

Description: Returns the current number of elements in the vector.

     Inputs: N/A

    Outputs: Number of elements in the vector
*******************************************************************************/
template<typename T>
unsigned int CVector<T>::size(void) const
{
  return Cur;
}

/*******************************************************************************
   Function: capacity()

Description: Returns the number of elements the vector can currently store

     Inputs: N/A

    Outputs: Number of elements the vector can store.
*******************************************************************************/
template<typename T>
unsigned int CVector<T>::capacity(void) const
{
  return Num;
}

/*******************************************************************************
   Function: empty()

Description: Is the vector empty?

     Inputs: N/A

    Outputs: 0 - There are 1+ elements in the vector
             1 - The vector is empty
*******************************************************************************/
template<typename T>
bool CVector<T>::empty(void) const
{
  return Cur == 0;
}

/*******************************************************************************
   Function: clear()

Description: Frees all the dynamic memory in the vector, and initilizes the
               requried variables for the vector to be used again.

     Inputs: N/A

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::clear(void)
{
  for(unsigned int i = 0; i < Cur; ++i)
    mData[i].~T();
  if(mData)
    Free(mData);
  Num   = 0;
  Cur   = 0;
  mData = 0;

  AllocData();
}

/*******************************************************************************
   Function: reserve()

Description: Increase the size of the vector. This should be used to stop
               additonal allocations, when the number of elements is known.

     Inputs: size - Number of elements the vector should be able to store.

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::reserve(unsigned int size)
{
  if(size >= Num)
  {
    Num = static_cast<int>(size / Growth) + 1;
    AllocData();
  }
}

/*******************************************************************************
   Function: resize()

Description: Increase the capacity of the vector by adding the specifed object
               until the requested size is meet.

     Inputs: size - Number of elements the vector should contain.
             c    - item to push back

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::resize(unsigned int size, T c)
{
  if(size > Cur)
    while(size > Cur)
      push_back(c);
  else
    while(size < Cur)
      pop_back();
}

template<typename T>
CVector<T> &CVector<T>::operator+=(const CVector<T> &r)
{
  unsigned int i, n = r.Cur;

  for(i = 0; i < n; ++i)
    push_back(r.mData[i]);

  return *this;
}

template<typename T>
CVector<T> CVector<T>::operator+(const CVector<T> &r) const
{
  return CVector<T>(*this) += r;
}



template<typename T>
void CVector<T>::RawSetCur(unsigned int n_elems)
{
  if(n_elems >= Num)
    reserve(n_elems + 1);

  Cur = n_elems;
}

/*******************************************************************************
   Function: AllocData()

Description: Private function that expands the memory that the vector contains.

     Inputs: N/A

    Outputs: N/A
*******************************************************************************/
template<typename T>
void CVector<T>::AllocData(void)
{
  if(!Num)
    Num = InitSize;
  Num = static_cast<int>(Num * Growth);
  mData = static_cast<T *>(Realloc(mData, sizeof(T) * (Num + 1)));
}

#endif
